//RotateList

//Given a list, rotate the list to the right by k places, where k is non - negative.
//For example : Given 1->2->3->4->5->nullptr and k = 2, return 4->5->1->2->3->nullptr.


#include<iostream>
using namespace std;

template<typename T>
struct SingleList{
	T _value;
	SingleList<T> *_next;
	SingleList(T value)
		:_value(value),
		_next(NULL)
	{}
};


template<typename T>
class Solution{
public:
	SingleList<T> *RotateList(SingleList<T> *head,int k)
	{
		if (head == NULL)
		{
			return head;
		}
		SingleList<T> *cur = head;
		SingleList<T> *tmp = head;   
		SingleList<T> *prev = NULL;  //prev of kth;
		--k; //from the first to k;
		while (k>0&&tmp)
		{
			--k;
			tmp = tmp->_next;
		}
		if (tmp == NULL||tmp->_next==NULL)
		{
			return head;
		}
		while (tmp->_next != NULL)
		{
			prev = cur;
			tmp = tmp->_next;
			cur = cur->_next;
		}
		tmp->_next = head;
		prev->_next = NULL;
		head = cur;
		return head;
	}
	void Display(SingleList<T> *&head)
	{
		if (head == NULL)
		{
			cout << "NULL";
			return;
		}
		SingleList<T> *cur = head;
		while (cur)
		{
			cout << cur->_value << "->";
			cur = cur->_next;
		}
		cout << "NULL"<<endl;
	}
};
int main()
{
	SingleList<int> *head = new SingleList<int>(1);
	SingleList<int> *list1 = new SingleList<int>(2);
	SingleList<int> *list2 = new SingleList<int>(3);
	SingleList<int> *list3 = new SingleList<int>(4);
	SingleList<int> *list4 = new SingleList<int>(5);
	SingleList<int> *list5 = new SingleList<int>(6);
	head->_next = list1;
	list1->_next = list2;
	list2->_next = list3;
	list3->_next = list4;
	list4->_next = list5;
	Solution<int> s;
	SingleList<int> *ret=s.RotateList(head,2);
	s.Display(ret);
	return 0;
}